//
// Description: 5724. 绝对差值和
// Created by Loading on 2021/4/4.
//

#include <bits/stdc++.h>

using namespace std;

int minAbsoluteSumDiff(vector<int> &nums1, vector<int> &nums2) {
    constexpr int MOD = 1e9 + 7;
    long long res = 0;

    //存储各位置绝对值
    vector<int> sub_array;
    //辅助set，按序储存nums1
    set<int> st;
    for (int i = 0; i < nums1.size(); ++i) {
        int sub = abs(nums1[i] - nums2[i]);
        st.insert(nums1[i]);
        sub_array.emplace_back(sub);
        res += sub;
    }

    //最大可以减掉的绝对值
    int max_sub = 0;
    int index = 0;
    for (auto &x : nums2) {
        //在set中二分查找第一个大于等于x的元素（寻找最接近x的元素，绝对值最小）
        /* 当时由于对lower_bound()方法不熟练，使用了其他算法，导致超时 */
        auto it = st.lower_bound(x);

        //替换nums1的当前位置后，绝对值的最小值
        int min_abs;
        if (it != st.end()) {//能够找到大于等于x的元素
            min_abs = abs(x - *it);
            //最接近x的元素可能小于x，故向前移动，找到最小值
            it--;
            if (it != st.end()) {
                min_abs = min(min_abs, abs(x - *it));
            }
        } else {//找不到大于等于x的元素，最接近的
            it--;
            min_abs = abs(x - *it);
        }

        //每次使用较大的值更新最大值，最终结果减掉这个值，使绝对差值和最小
        max_sub = max(sub_array[index++] - min_abs, max_sub);
    }

    return (int) (res - max_sub) % MOD;
}

int main() {
    vector<int> nums1 = {56, 51, 39, 1, 12, 14, 58, 82, 18, 41, 70, 64, 18, 7, 44, 90, 55, 23, 11, 79, 59, 76, 67, 92,
                         60, 80, 57, 11, 66, 32, 76, 73, 35, 65, 55, 37, 38, 26, 4, 7, 64, 84, 98, 61, 78, 1, 80, 33, 5,
                         66, 32, 30, 52, 29, 41, 2, 21, 83, 30, 35, 21, 30, 13, 26, 36, 93, 81, 41, 98, 23, 20, 19, 45,
                         52, 25, 51, 52, 24, 2, 45, 21, 97, 11, 92, 28, 37, 58, 29, 5, 18, 98, 94, 86, 65, 88, 8, 75,
                         12, 9, 66};
    vector<int> nums2 = {64, 32, 98, 65, 67, 40, 71, 93, 74, 24, 49, 80, 98, 35, 86, 52, 99, 65, 15, 92, 83, 84, 80, 71,
                         46, 11, 26, 70, 80, 2, 81, 57, 97, 12, 68, 10, 49, 80, 24, 18, 45, 72, 33, 94, 60, 5, 94, 99,
                         14, 41, 25, 83, 77, 67, 49, 70, 94, 83, 55, 17, 61, 44, 50, 62, 3, 36, 67, 10, 2, 39, 53, 62,
                         44, 72, 66, 7, 3, 6, 80, 38, 43, 100, 17, 25, 24, 78, 8, 4, 36, 86, 9, 68, 99, 64, 65, 15, 42,
                         59, 79, 66};

//    vector<int> nums1 = {1, 10, 4, 4, 2, 7};
//    vector<int> nums2 = {9, 3, 5, 1, 7, 4};

    cout << minAbsoluteSumDiff(nums1, nums2) << endl;
}